package sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {12, 45, 2, 45, 32, 11, 32, 67, 10, 5, 3};
//        int[] a = {12, 3, 2, 45, 32, 11, 32, 67, 10, 5, 45};
//        int[] a = {12, 3, 2, 5, 10, 11, 32, 67, 32, 45, 45};
//        int[] a = {11, 3, 2, 5, 10, 12, 32, 67, 32, 45, 45};

        sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    /*
        1. 用left和right标出处理范围，最初从0到length-1范围进行处理
        2. 选取第一个值作为基准值
        3. 下标i和j，分别从left和right开始
        4. j循环向左移动，如果找到>=基准值的值，继续向左，否则停下
        5. i循环向右移动，如果找到<=基准值的值，继续向右，否则停下
        6.两个都停下后如果i<j 则把两个位置值交换
        8. i和j重合时，循环停止
        9. 基准值放入i位置
        10. 递归处理左侧的 left到i-1 范围
        11. 递归处理右侧的 i+1到right 范围

        最简问题：一个值（left和right重合），没有值（left>right）
     */
    private static void sort(int[] a, int start, int end) {
        if (start>=end){
            return;
        }
        int i = start;
        int j = end;
        int tem = a[i];
        while (i < j) {//i,j不重合就继续执行
            while (a[j] >= tem && j > i) {
                j--;
            }
            while (a[i] <= tem && i < j) {
                i++;
            }
            if (i<j){
                int t = a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        a[start] = a[i];
        a[i]=tem;
        sort(a,start,j-1);
        sort(a,j+1,end);
    }
}
